#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (int)b; ++i)
const int MV = 205, INF = 0x7f7f7f7f;
typedef int Mat[MV][MV];
int sz;
void matmul(Mat A, Mat B, Mat C) {
  static Mat m;
  memset(m, 0x7f, sizeof(Mat));
  rep(i, 0, sz) rep(j, 0, sz) rep(k, 0, sz) {
    if (A[i][k] != INF && B[k][j] != INF)
      m[i][j] = min(m[i][j], A[i][k] + B[k][j]);
  }
  memcpy(C, m, sizeof(Mat));
}
void matpow(Mat A, int n, Mat r) {
  Mat a;
  memcpy(a, A, sizeof(a));
  memcpy(r, A, sizeof(Mat));
  --n;
  for (int i = 0; (1 << i) <= n; ++i) {
    if (n & (1 << i)) matmul(r, a, r);
    matmul(a, a, a);
  }
}
map<int, int> ID;
int getId(int u) {
  if (!ID.count(u)) ID[u] = sz++;
  return ID[u];
}
Mat G, Ans;
int main() {
  int N, T, S, E;
  cin >> N >> T >> S >> E;
  sz = 0, memset(G, 0x7f, sizeof(G));
  for (int i = 1, u, v, w; i <= T; ++i) {
    cin >> w >> u >> v;
    u = getId(u), v = getId(v);
    G[u][v] = G[v][u] = min(G[u][v], w);
  }
  matpow(G, N, Ans);
  cout << Ans[getId(S)][getId(E)] << endl;
}
